import java.util.Stack;

public class Sort {

    /*
    时间复杂度
                最好情况：数据刚好有序  1 2 3 4 5 6     O（n）
                最坏情况： 数据完全逆序 6 5 4 3 2 1     O（n^2）
                结论：当给的数据越有序，排序越快
    空间复杂度
                O（1）
                稳定性：稳定的排序
                 一个本身就是稳定的排序  是可以实现为不稳定的排序的
                 但是相反 一个本身就不稳定的排序  是不可能实现为稳定的排序的*/
    //直接插入法：
    public  static  void insertSort(int[]array){
        for (int i = 1; i <array.length ; i++) {
            int tmp=array[i];
            int j;
            for (j = i-1; j >=0 ; j--) {
               if(array[j]>tmp){
                   array[j+1]=array[j];
               }else{
                   //array[j+1]=tmp;
                   break;
               }
            }
            array[j+1]=tmp;
        }
    }
    /*希尔排序：
              时间复杂度n^1.3-n^1.5
              空间复杂度O(1)
              稳定性:不稳定排序
    * */
    //希尔排序的实现
    public  static  void shell(int[]array,int gap){
        for (int i = gap; i <array.length ; i++) {
            int tmp=array[i];
            int j=i-gap;
            for(;j>=0;j-=gap){
                if(array[j]>tmp){
                    array[j+gap]=array[j];
                }else{
                    break;
                }
            }
            array[j+gap]=tmp;
        }


    }
    //希尔排序gap的确定
    public  static  void shellSort(int []array){
        int gap= array.length;
        while (gap>1){
            gap/=2;
            shell(array,gap);
        }

    }
    // 时间复杂度：不管最好还是最坏 都是O(n^2)
    //  空间复杂度：O(1)
    //  稳定性：不稳定的排序
    //选择排序的实现      假设数组第一个为最小值，从后边循环与最小值比较，小于就放到前边，
    public  static  void selectSort(int []array){
        for (int i = 0; i < array.length ; i++) {
            int minIndex=i;
            for (int j = i+1; j < array.length ; j++) {
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }

            }
            swap(array,minIndex,i);

        }

    }
    //写一个方法，用来交换数组中i和j下标的值
    private  static  void swap(int []array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;

    }
    //第二种选择排序，改进的是每次循环，都同时找出最小值和最大值，然后交换
    public  static  void selectSort1(int []array){
        int left=0;
        int right= array.length-1;
        while (left<right){
            int minIndex=left;
            int maxIndex=left;
            for(int i=left+1;i<=right;i++){
                if(array[i]<array[minIndex]){
                    minIndex=i;
                }
                if(array[i]>array[maxIndex]){
                    maxIndex=i;
                }
            }
            swap(array,left,minIndex);
            if(maxIndex==left){
                maxIndex=minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }
    // 时间复杂度：
    //   O(n*logN)        N^1.3 -->
    //  空间复杂度：O(1)
    // 稳定性：不稳定的
    //    数据量非常 大的时候 堆排 一定比希尔快
    public  static  void heapSort(int[]array){
        createBigHeap(array);//创建大根堆
        int end= array.length-1;
        while (end>0){
            swap(array,0,end);//最大的根节点与最后一个节点交换
            siftDown(array,0,end);//重新调整交换后的堆，使之重新成为大根堆
        }




    }
    private  static  void  createBigHeap(int[]array) {
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
            siftDown(array, parent, array.length);
        }


    }
    public  static  void siftDown(int []array,int parent,int end){
        int child=2*parent+1;
        while (child<end){
            if(child+1<end&&array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;

            }else {
                break;
            }
        }

    }
    //冒泡排序
    //时间复杂度：O（n^2）   空间复杂度：O（1）  稳定
    public  static  void bubbleSort(int[] array){
        for (int i = 0; i < array.length ; i++) {
            boolean flg=false;//做标记  防止一开始就有序，做无为的比较
            for (int j = 0; j < array.length-i ; j++) {
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }

            }
            if(!flg){
                return ;
            }

        }
    }
    public  static  void quickSort(int[]array){
        quick(array,0,array.length-1);


    }
    private  static  void quick(int[]array,int start,int end){
        if(start>=end)return;
        int pivot=partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);

    }
    private  static  int partition(int[]array,int left,int right){
        int key=array[left];
        int i=left;
        while (left<right){
            while (left<right&&array[right]>=key){
                right--;//right 下标一定是 比key小的数据
            }
        }
        while (left < right && array[left] <= key) {//这里为什么要取等号
            left++;  //left 下标一定是 比key大的数据
        }
        swap(array,left,right);//当left和right相遇时，
        swap(array,left,i);
        return left;
    }
    public  static  void quickSortNor(int[]array){//用非递归实现快速排序
        Stack<Integer>stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        int piovt=partition(array,left,right);
        if(piovt-1>left){
            stack.push(left);
            stack.push(piovt-1);

        }
        if(piovt+1<right){
            stack.push(piovt+1);
            stack.push(right);

        }
        while (!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();
            piovt=partition(array,left,right);
            if(piovt-1>left){
                stack.push(left);
                stack.push(piovt-1);

            }
            if(piovt+1<right){
                stack.push(piovt+1);
                stack.push(right);
            }
        }


    }
    //归并排序
    public  static  void  mergerSort(int[]array){
        mergerSortFunc(array,0,array.length-1);
    }
    private  static  void mergerSortFunc(int[]array,int left,int right){
        if(left>=right)return ;
        int mid=(left+right)/2;
        mergerSortFunc(array,left,mid);
        mergerSortFunc(array,mid+1,right);
        merge(array,left,right,mid);
    }

    private  static  void merge(int[] array, int left, int right, int mid){
        int s1=left;
        int s2=mid+1;
        int[]tmpArr=new int[right-left+1];
        int k=0;
        while(s1<=mid&&s2<=right){
            if(array[s2]<=array[s1]){
                tmpArr[k++]=array[s2++];
            }else {
                tmpArr[k++]=array[s1++];
            }
        }
        while (s1<=mid){
            tmpArr[k++]=array[s1++];
        }
        while (s2<=right){
            tmpArr[k++]=array[s2++];
        }
        for (int i = 0; i < tmpArr.length; i++) {
            array[i+left] = tmpArr[i];
        }
    }
    //计数排序
    public  static  void countSort(int[]array){
        int minVal=array[0];
        int maxVal=array[0];
        //1、求当前数组的最大值  和  最小值
        for (int i = 1; i < array.length; i++) {
            if(array[i] < minVal) {
                minVal = array[i];
            }
            if(array[i] > maxVal) {
                maxVal = array[i];
            }
        }
        int []count=new int[maxVal-minVal+1];
        for (int i = 0; i < array.length; i++) {
            count[array[i]-minVal]++;//计数

        }
        int index=0;
        for (int i = 0; i <count.length ; i++) {
            while (count[i]>0){//计数大于0的出数
                array[index]=i+maxVal;
                index++;
                count[i]--;
            }

        }

    }




}
